package problem;

import java.util.ArrayList;
import java.util.List;

public class S_131 {
    //分割回文串
    /*给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。*/
    class Solution {
        public List<List<String>> partition(String s) {
            List<List<String>> res=new ArrayList<>();
            List<String> tmp=new ArrayList<>();
            backtrack(s,res,tmp);
            return res;
        }
        public void backtrack(String s,List<List<String>> res,List<String> tmp){
            if(s==null||s.length()==0) res.add(new ArrayList<>(tmp));
            for(int i=1;i<=s.length();i++){      //第一个要切割的子字符串的长度
                if(isPalindrome(s.substring(0,i))){
                    tmp.add(s.substring(0,i));
                    backtrack(s.substring(i,s.length()),res,tmp);     //左闭右开区间
                    tmp.remove(tmp.size()-1);   //回溯删除最后一个元素
                }
            }
        }
        public boolean isPalindrome(String s){
            if(s.length()==1) return true;
            int i=0,j=s.length()-1;
            while(i<j){
                if(s.charAt(i)==s.charAt(j)){
                    i++;j--;
                }
                else return false;
            }
            return true;
        }
    }
}
